/**
 * 152.乘积的最大子数组
 */
public class Exerciser3 {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        // 创建 dp 表
        int[] f = new int[n + 1]; // 乘积最大的非空连续 子数组
        int[] g = new int[n + 1]; // 乘积最小的非空连续 子数组
        // 初始化，因为是乘以f(i - 1) g(i - 1)位置的值，所以将其初识为1
        f[0] = g[0] = 1;
        int ret = Integer.MIN_VALUE;
        for(int i = 1;i <= n;i++) {
            // 这是 乘积最大值子数组，长度=1 -> nums[i - 1]（本身），
            //                      长度>1 -> nums[i - 1] > 0为f[i - 1] * nums[i - 1]和nums[i - 1] < 0为g[i - 1] * nums[i - 1])
            // 把这些情况都计算出来，直接比较最大值就可以了
            f[i] = Math.max(nums[i - 1],Math.max(f[i - 1] * nums[i - 1],g[i - 1] * nums[i - 1]));
            // 这是 乘积最大小值子数组，长度=1 -> nums[i - 1]（本身），
            //                      长度>1 -> nums[i - 1] < 0为f[i - 1] * nums[i - 1]和nums[i - 1] > 0为g[i - 1] * nums[i - 1])
            // 把这些情况都计算出来，直接比较最小值就可以了
            g[i] = Math.min(nums[i - 1],Math.min(g[i - 1] * nums[i - 1],f[i - 1] * nums[i - 1]));
            ret = Math.max(ret,f[i]);
        }
        return ret;
    }
}
